HW#2 --- last modified March 02 2019 21:31:07..

Solution set.

Due date: Oct 2

Files to be submitted:
  Hw2.tex
  HornChecker.zip

Purpose: To be able to classify problems as decidable or undecidable. To gain some understanding of circuits.

Related Course Outcomes:

Problems (1) and (2) concerns Learning Outcome (1): Exhibit a simulation of one machine model with another.

Problem (3) is connected to leaning outcome (2) Give a minimal classification of the complexity of a computational problem as being in one of the class ALogTime, L, P, NP, coNP, some level of the polynomial hierarchy, PSPACE, E, EXPTIME, decidable, undecidable. In this case, we are concerned about decidable versus undecidable.

The coding part of the assignment is connected to learning outcome (2) mentioned above as well as connected to the background needed for learning outcome (6) Explain at least one circuit lower bound technique such as Razborov's techniques for monotone circuits.

Specification:

1. Consider the model of nondeterminism where the number of possible transitions one has reading the same symbol in the same state is at most two. Show this model can simulate the usual model of nondeterminism with at most a polynomial time slow down.

2. Identify the natural numbers with binary strings in a reasonable way. Consider the following functions from tuples of natural numbers to naturals: 0 -- the function which on any input outputs 0. 1 -- the function which on any input outputs 1. x + y which on input a pair x,y outputs their sum. x * y -- which on input a pair x,y outputs their product. 2^x -- which on input x outputs 1 followed by x zero's. (i) Show that each of these functions is computable by a Turing Machine. (ii) Show that if f(x₁,...,x_i-1,x_i,x_i+1..x_k) and g(y₁,..y_m) are functions computable by a Turing machine, then so is the composition f(x₁,...,x_i-1,g(y₁,..y_m),x_i+1..x_k). (iii) Given two functions g(x₁,...x_k) and h(y,z, x₁,...x_k) let f be the unique function such that

f(0,x₁,...x_k) = g(x₁,...x_k)

f(n+1, x₁,...x_k) = h(n, f(n, x₁,...x_k), x₁,...x_k)

Here f is said to be defined by primitive recursion from g and h. Show that if f is defined by primitive recursion form g and h, and g and h are computable, then f is computable. (iv) Give a function f from the tuples of naturals to naturals, define μ y f(y, x₁,...x_k)=z to be the least y such that f(y, x₁,...x_k) = z, if such a y exists and is undefined otherwise. Functions which are not defined on all inputs are called partial functions. Suppose f is computable show that there is a Turing machine which computes a y satisfying μ y f(y, x₁,...x_k) if such a y exists and runs forever otherwise. (v) The μ-recursive functions are the smallest class of partial functions which contain the functions of part (i) and which are closed under composition, primitive recursion, and the μ-operator of part (iv). Note my definition is a variation on the standard one. We have just argued that such functions can be simulated on a Turing machine. Now let U(x,y) be a fixed universal Turing Machine with inputs x and y. This machine computes some partial function. Show how to represent this partial function as a μ-recursive function.

3. Do problem 3.4.1 out of the book.

For the coding part of the assignment, I would like you to implement the polynomial time algorithm from class for checking if a set of Horn clauses is satisfiable. I will assume the Horn clauses are stored in some file with one clause per line. A line has the format int:int,int,int,...,int. For example:

21:1,45,2

This represent the Horn clause x₂₁ OR NOT(x₁) OR NOT(x₄₅) OR NOT(x₂). If a line begins with a : then it is assumed all variables in the clause are negated. I will test your program on the command line with a line like:

java HornChecker file.txt

Here HornChecker should be the name of your program and file.txt will be my file of Horn clauses. You program should output `yes' if the set of clauses is satisfiable and `no' otherwise. It should do its calculations based on the algorithm from class.

Point Breakdown